Constraint Propagation

释义 Definition

约束传播：在约束满足问题（CSP）等场景中，把已知约束带来的限制“传递”到相关变量上，逐步缩小变量可能取值范围，从而更快发现可行解或及早判定无解。（在数独、排课、图着色、逻辑推理与部分类型推断中常见）

发音 Pronunciation

/kənˈstreɪnt ˌprɑːpəˈɡeɪʃən/

例句 Examples

Constraint propagation can quickly eliminate impossible values in a Sudoku grid.
约束传播可以快速排除数独格子里不可能的候选数字。

By enforcing arc consistency, the solver uses constraint propagation to prune the search space before backtracking, which often makes hard scheduling problems feasible.
通过施加弧一致性，求解器在回溯之前利用约束传播剪枝搜索空间，这往往能让困难的排程问题变得可解。

词源 Etymology

constraint 源自拉丁语 constringere（“绑紧、限制”），引申为“限制条件、约束”；propagation 源自拉丁语 propagare（“扩散、繁殖、传播”）。合起来表示：把“限制条件”在变量之间传播/扩散，以推导出更多限制并缩小可能性。

相关词 Related Words

• Arc Consistency
• Backtracking
• Constraint Satisfaction Problem
• Domain Reduction
• Inference
• Local Consistency
• Pruning
• SAT Solver

文学与著作中的用例 Literary Works

• Artificial Intelligence: A Modern Approach（Russell & Norvig）——在约束满足问题章节中讨论约束传播与一致性方法。
• Principles of Constraint Programming（Krzysztof Apt）——系统介绍约束传播、传播器（propagators）与一致性理论。
• Constraint Processing（Rina Dechter）——涵盖约束网络中的传播算法与复杂度分析。
• Handbook of Constraint Programming（Rossi, van Beek, Walsh 编）——多篇章节使用并扩展“constraint propagation”概念与实践。